「上次的幾題，做得還蠻順利吧？」

「對呀！幸好都是一些相對比較簡單的題目」隨著一起合作解題的次數變多，菁菁和曉欣的默契越來越好。除了曉欣明顯的進步之外，菁菁也對 Kotlin 的一些寫法越來越熟悉。

「今天我們來處理一個比較特別的資料結構：樹」

「樹？」

「曉欣你應該不知道，這個是資訊系必修會教到的資料結構。

不過夏天姐，Kotlin 又不像 C 或者 C++ 這樣有指標，要怎麼呈現樹的資料結構呢？」

「看題目就知道囉」夏天打開了 100. Same Tree

「原來是這樣處理」菁菁研究起了題目的註解

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */

「所以是透過 reference 的方式，來指定左邊的節點和右邊的節點。」

graph TB;
    A((1))-->B((2))
    A-->C((3))

「咦，這樣不確定有多少東西要處理的話，該怎麼用迴圈做呢⋯⋯」

「也可以用 while 迴圈處理沒錯，不過更直觀的解法，還是用到遞迴處理，會更簡單一點。

你注意看的話，在樹的資料結構裡，每個分支下去的內容，其實也是一個樹的結構。

所以樹狀的資料結構，非常適合用遞迴處理。

我們先想看看，最小的樹來說，怎麼知道兩棵樹是不相等的？」

「其中一個是 null，但是另一棵樹不是 null！」

「沒錯！再來呢？」

「嗯⋯⋯兩個節點的 val 不相同？」

「沒錯沒錯！反過來說，如果兩棵樹都是 null，那麼就是相等的。

如果兩邊都不是 null，值也相同，那麼我們就往下比較左邊的子樹和右邊的子樹了」夏天邊說邊寫下邏輯

class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        return if (p == null && q == null) {
            true
        } else if ((p == null) || (q == null)) {
            false
        } else if (p!!.`val` != q!!.`val`) {
            false
        } else {
            isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
        }
    }
}

「夏天姐！那是不是也可以這樣寫」

class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean = when {
        p == null && q == null -> true
        (p == null) || (q == null) -> false
        p!!.`val` != q!!.`val` -> false
        else -> isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    } 
}

「沒錯！曉欣越來越厲害囉！」

「今天樹的結構要花一點時間思考，我們就先一個題目就好了！」